package com.heima.leetcode.practice;

import com.heima.leetcode.datastructure.linkedlist.IsPalindrome;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 234. 回文链表
 * @date 2025/2/9 22:53
 */
public class E234 {

    /**
     * <h3>方法一：快慢指针找中点，然后反转右半部分链表，然后比较</h3>
     *
     * @param head 头指针
     * @return 是否是回文链表
     */
    public boolean isPalindrome1(ListNode head) {
        ListNode median = middle(head);
        ListNode headOfRight = reverse(median);
        while (headOfRight != null) {
            if (head.val != headOfRight.val) return false;
            head = head.next;
            headOfRight = headOfRight.next;
        }
        return true;
    }

    /**
     * 快慢指针找中点
     *
     * @param head 头指针
     * @return 是否是回文链表
     */
    private ListNode middle(ListNode head) {
        ListNode p1 = head, p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

    /**
     * 反转链表
     *
     * @param head 头指针
     * @return 是否是回文链表
     */
    private ListNode reverse(ListNode head) {
        ListNode sentinel = new ListNode(-1);
        while (head != null) {
            ListNode next = head.next;
            head.next = sentinel.next;
            sentinel.next = head;
            head = next;
        }
        return sentinel.next;
    }

    /**
     * <h3>方法二：快慢指针找中点的同时反转左半部分链表，然后比较</h3>
     *
     * @param head 头指针
     * @return 是否是回文链表
     */
    public boolean isPalindrome2(ListNode head) {
        // 找到中间节点的同时让前半链表反转
        ListNode p1 = head;
        ListNode p2 = head;
        ListNode oldHead = head;
        ListNode newHead = null;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            // 前半链表反转
            oldHead.next = newHead;
            newHead = oldHead;
            oldHead = p1;
        }
        // 让前半链表和后半链表进行一一比较
        // 判断是否是奇数个节点
        if (p2 != null) p1 = p1.next;
        // 一一比较
        while (newHead != null) {
            if (newHead.val != p1.val) return false;
            newHead = newHead.next;
            p1 = p1.next;
        }
        return true;
    }
}
